package com.leetcode.算法策略相关.动态规划;

import lombok.Data;

import java.util.Scanner;

/**
 * @author: xiaomi
 * @date: 2022/5/29
 * @description:
 * https://www.acwing.com/problem/search/1/
 * https://www.acwing.com/problem/content/description/8/
 */
public class B_二维费用背包问题 {
    static B_二维费用背包问题 action = new B_二维费用背包问题();

    public static void main(String[] args) {
//        test1();

        //二维费用01 背包
        int type = 1;
        //二维费用完全 背包
        type = 2;
//        test2(type);
        //四维费用完全背包 -- 如果使用五维数组，就会发现很慢了！所以不使用这种方案！
        test3();
    }

    static void test1() {
        //
        Machine42Way[] arr = new Machine42Way[]{null, new Machine42Way(35, 62), new Machine42Way(18, 20), new Machine42Way(18, 21)};
        int size = 100;
        int[][][] dp = new int[arr.length + 1][size + 1][size + 1];
        for (int i = 1; i <= arr.length; i++) {
            for (int j = 1; j <= size; j++) {
                for (int k = 1; k <= size; k++) {
                    if (j < arr[i].bom1 || k < arr[i].bom2) {
                        // 客观条件限制，不能选择当前物品N
                        dp[i][j][k] = dp[i - 1][j][k];
                    } else {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - arr[i].bom1][k - arr[i].bom2] + 1);
                    }
                }
            }
        }
        int max = dp[arr.length][size][size];

        //System.out.println("res = " + res);
    }

    /**
     * 二位费用 01/完全 背包的解法
     *
     * @param type
     */
    static void test2(int type) {
        // N个物品
        int N;

        // 背包体积
        int V;

        // 背包承受最大的重量
        int M;

        // 每个物品的体积
        int[] v;

        // 每一个物品的重量
        int[] m;

        // 每一个物品的价值
        int[] w;

        // start input
        Scanner input = new Scanner(System.in);
        N = input.nextInt();
        V = input.nextInt();
        M = input.nextInt();
        v = new int[N + 1];
        m = new int[N + 1];
        w = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            v[i] = input.nextInt();
            m[i] = input.nextInt();
            w[i] = input.nextInt();
        }
        input.close();
        B_二维费用背包问题 solution = new B_二维费用背包问题();
        if (type == 1) {
            System.out.println(solution.two_dimension_knapsack_problem_1(N, V, M, v, m, w));
            //System.out.println(solution.two_dimension_knapsack_problem_2(N,V,M,v,m,w));
        } else {
            System.out.println(solution.two_dimension_knapsack_complete_problem_1(N, V, M, v, m, w));
        }


        //System.out.println("res = " + res);
    }

    /**
     * 使用大佬的方式，编写四维完全背包
     */
    static void test3() {
        int N = 3;
        int bomA1 = 100;
        int bomA2 = 100;
        int bomA3 = 100;
        int bomA4 = 100;

        int[] a1 = {0, 35, 62, 15, 0, 1};
        int[] a2 = {0, 18, 20, 27, 0, 1};
        int[] a3 = {0, 18, 21, 12, 14, 1};

        int[] bom1 = {0, 35, 18, 18};
        int[] bom2 = {0, 62, 20, 21};
        int[] bom3 = {0, 15, 27, 12};
        int[] bom4 = {0, 0, 0, 14};
        int[] value = {0, 1, 1, 1};


        int[][][][][] dp = new int[N + 1][bomA1 + 1][bomA2 + 1][bomA3 + 1][bomA4 + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= bomA1; j++) {
                for (int k = 1; k <= bomA2; k++) {
                    for (int l = 1; l <= bomA3; l++) {
                        for (int m = 1; m <= bomA4; m++) {
                            if (j < bom1[i] || k < bom2[i] || l < bom3[i] || m < bom4[i]) {
                                // 客观条件限制，不能选择当前物品N
                                //dp[i][j][k] = dp[i - 1][j][k];
                                dp[i][j][k][l][m] = dp[i - 1][j][k][l][m];
                            } else {
//                                dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i][j - v[i]][k - m[i]] + w[i]);
                                dp[i][j][k][l][m] = Math.max(dp[i - 1][j][k][l][m],
                                        dp[i][j - bom1[i]][k - bom2[i]][l - bom3[i]][m - bom4[i]] + value[i]);
                            }
                        }
                    }
                }
            }
        }
        int max = dp[N][bomA1][bomA2][bomA3][bomA4];


        //System.out.println("res = " + res);
    }

    /**
     * 传统解法，即没有优化的解法，这个解法对于n种约束需要构建一个n维的dp矩阵
     * input:
     * N V M
     * 3 100 100
     * vi mi valuei
     * 35 62 1
     * 18 20 1
     * 18 21 1
     *
     * @param N 题目提供N个物品
     * @param V 背包的总体积
     * @param M 背包承受最大的重量
     * @param v 每个物品的体积 v[i],长度为N+1,第0位无用
     * @param m 每个物品的重量 m[i],长度为N+1,第0位无用
     * @param w 每个物品的价值 w[i],长度为N+1,第0位无用
     * @return 在给定物品，背包总体积以及背包最大重量的情况下，背包能装的物品的最高总价值
     */
    public int two_dimension_knapsack_problem_1(int N, int V, int M, int[] v, int[] m, int[] w) {
        int[][][] dp = new int[N + 1][V + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= V; j++) {
                for (int k = 1; k <= M; k++) {
                    if (j < v[i] || k < m[i]) {
                        // 客观条件限制，不能选择当前物品N
                        dp[i][j][k] = dp[i - 1][j][k];
                    } else {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - v[i]][k - m[i]] + w[i]);
                    }
                }
            }
        }
        return dp[N][V][M];
    }

    /**
     * 二维费用完全背包！
     *
     * @param N
     * @param V
     * @param M
     * @param v
     * @param m
     * @param w
     * @return
     */
    public int two_dimension_knapsack_complete_problem_1(int N, int V, int M, int[] v, int[] m, int[] w) {
        int[][][] dp = new int[N + 1][V + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= V; j++) {
                for (int k = 1; k <= M; k++) {
                    if (j < v[i] || k < m[i]) {
                        // 客观条件限制，不能选择当前物品N
                        dp[i][j][k] = dp[i - 1][j][k];
                    } else {
//                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - v[i]][k - m[i]] + w[i]);
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i][j - v[i]][k - m[i]] + w[i]);
                    }
                }
            }
        }
        return dp[N][V][M];
    }


    /**
     * 机型
     */
    @Data
    static class Machine42Way {

        private int bom1;
        private int bom2;

        public Machine42Way() {
        }

        public Machine42Way(int bom1, int bom2) {
            this.bom1 = bom1;
            this.bom2 = bom2;
        }
    }
}
